package xyz.robinbingo.leetcode.a20.b05.c27;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int result = 0;
        Map<Integer, Integer> map = new HashMap<>();
        // 空的时候，可以认为和为0，这样最少再有一个0就行了
        // 其他的则至少有2个
        map.put(0, 1);
        int sum = 0;
        for (int value : A) {
            sum += value;
            int mol = (sum % K + K) % K;
            Integer count = map.getOrDefault(mol, 0);
            result += count;
            map.put(mol, count + 1);
        }
        return result;
    }
}